package 排序;

import java.util.Arrays;

/*
 * 每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。
 * 速度优于选择排序
 */
public class 插入排序 {

    public static void insertSort(int[] a) {
        int n = a.length;
        for (int i = 1; i < n; i++) {
            // 为了将当前元素插入到已经排序的数组中需要从后往前遍历
            for (int j = i; j > 0 ; j--) {
                if (a[j] < a[j - 1]) {
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                } else {
                    continue;
                }
            }
        }
    }

    public static void main(String[] args) {
//        int[] s = {4, 6, 1, 2, 3, 0};
        int[] s = {9,7,1,-8,36,-18,100};
        System.out.println(Arrays.toString(s));
        insertSort(s);
        System.out.println(Arrays.toString(s));

    }
}
